package com.xsherl.leetcode.solution;

public class WildcardMatching {

    /**
     * 动态规划
     * f[i][j] = {
     *     f[i - 1][j - 1], s[i - 1] == p[j - 1] || p[j - 1] == '?'
     *     f[i][j - 1] || f[i - 1][j], p[j - 1] == '*' && s[i - 1] != p[j - 1]
     * }
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        // 当s和p都是空字符串时，两个字符串是匹配的
        f[0][0] = true;
        // p开头的‘*’和空字符串都匹配
        int i = 1;
        while (i <= n && p.charAt(i - 1) == '*'){
            f[0][i] = true;
            i++;
        }
        for (int j = 1; j <= m; ++j){
            for (int k = 1; k <= n; ++k){
                if (s.charAt(j - 1) == p.charAt(k - 1) || p.charAt(k - 1) == '?'){
                    f[j][k] = f[j - 1][k - 1];
                } else if (p.charAt(k - 1) == '*'){
                    f[j][k] = f[j][k - 1] || f[j - 1][k];
                }
            }
        }
        return f[m][n];
    }

    public static void main(String[] args) {
        String s = "";
        String p = "**";
        boolean match = new WildcardMatching().isMatch(s, p);
        System.out.println(match);
    }
}
